;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Copyright 2021 fanguangping
; 
; Licensed under the Apache License, Version 2.0 (the "License");
; you may not use this file except in compliance with the License.
; You may obtain a copy of the License at
; 
;     http://www.apache.org/licenses/LICENSE-2.0
; 
; Unless required by applicable law or agreed to in writing, software
; distributed under the License is distributed on an "AS IS" BASIS,
; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
; See the License for the specific language governing permissions and
; limitations under the License.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

#lang racket

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Sorted class
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(require avl)

(require "../common/constants.scm")
(require "../common/messages.scm")
(require "../common/utils.scm")
(require "Object.scm")

(provide (all-defined-out))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Make Sorted class
;   - sort by avl tree
;   - sorted nodes are key-value pairs
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (MAKE-Sorted self avl-tree less-equal-p equal-p)
  (lambda (message)
    (cond
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Getters
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +G-Sorted-avl-tree+)
       (lambda () avl-tree))
      
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Init sorted elements
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-init+)
       (lambda ()
         (set! avl-tree (make-custom-avl
                         (lambda (a b) (less-equal-p (car a) (car b)))
                         (lambda (a b) (equal-p (car a) (car b)))))))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Sorted elements are empty
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-empty+)
       (lambda ()
         (avl-empty? avl-tree)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Add node to sorted elements
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-add+)
       (lambda (node)
         (avl-add! avl-tree node)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Remove node from sorted elements
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-remove+)
       (lambda (node)
         (avl-remove! avl-tree node)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Select node from sorted elements
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-find+)
       (lambda (node)
         (avl-search avl-tree (cons (car node) +nil+))))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Contains key
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-contains+)
       (lambda (node)
         (avl-contains? avl-tree node)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Union two sorted object
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-union+)
       (lambda (other)
         (let ((u (create-instance MAKE-Sorted (avl-copy avl-tree) less-equal-p equal-p)))
           (for/list ((n (in-avl (ask other +G-Sorted-avl-tree+))))
             (sorted-add! u n))
           u)))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; Sorted elements
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Sorted-elements+)
       (lambda ()
         (avl->list avl-tree)))
      
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: equals
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-equals+)
       (lambda (other)
         (let ((self-lst (avl->list avl-tree))
               (other-lst (avl->list (ask other +G-Sorted-avl-tree+))))
           (cond
             ((not-equal? (length self-lst) (length other-lst)) +false+)
             ((andmap (lambda (a b) (object-equals? (car a) (car b))) self-lst other-lst) +true+)
             (else +false+)))))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: hash code
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-hash-code+)
       (lambda ()
         '()))
      
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; TODO: to string
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-to-string+)
       (lambda ()
         (string-append "Sorted: ["
                        (string-join (map object-to-string (avl->list avl-tree)) ", ")
                        "]")))

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ; type
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      ((= message +M-Object-type+)
       (lambda () 'Sorted))
      
      (else +nil+))))

(define (CREATE-Sorted less-equal-p equal-p)
  (let ((t (create-instance MAKE-Sorted +nil+ less-equal-p equal-p)))
    (ask t +M-Sorted-init+)
    t))

(define (sorted-empty? s)
  (ask s +M-Sorted-empty+))
(define (sorted-add! s node)
  (ask s +M-Sorted-add+ node))
(define (sorted-remove! s node)
  (ask s +M-Sorted-remove+ node))
(define (sorted-find s node)
  (ask s +M-Sorted-find+ node))
(define (sorted-contains? s node)
  (ask s +M-Sorted-contains+ node))
(define (sorted-union s other)
  (ask s +M-Sorted-union+ other))
(define (sorted-elements s)
  (ask s +M-Sorted-elements+))
